package com.fengdi.book.middle;

import java.util.*;
import java.util.stream.Collectors;

public class SortAndSearch {
    public static class FindKthLargest {
        public static int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length - k];
        }
    }

    public static class FindPeakElement {
        public int findPeakElement(int[] nums) {
            return this.binarySearch(nums, 0, nums.length - 1);
        }

        public int binarySearch(int[] nums, int left, int right) {
            int mid = left + (right - left) / 2;
            if(left < right) {
                if(nums[mid] > nums[mid + 1]) {
                    return this.binarySearch(nums, left, mid);
                }else {
                    return this.binarySearch(nums, mid + 1, right);
                }
            }
            return mid;
        }

    }

    public static class SearchRange {
        public int[] searchRange(int[] nums, int target) {
            if(nums.length == 0) return new int[]{-1,-1};
            int[] result = new int[]{-1, -1};
            this.binarySearch(nums, target, 0, nums.length - 1, result);
            return result;
        }

        public void binarySearch(int[] nums, int target, int left, int right, int[] result) {
            if(left > right) return;
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                result[0] = findBegin(nums, mid, target);
                result[1] = findEnd(nums, mid, target);
            }
            if(nums[mid] > target) {
                this.binarySearch(nums, target, left, mid - 1, result);
            }else {
                this.binarySearch(nums, target, mid + 1, right, result);
            }
        }

        private int findBegin(int[] nums, int begin, int target) {
            while(begin >= 0 && nums[begin] == target) {
                begin--;
            }
            return ++begin;
        }

        private int findEnd(int[] nums, int end, int target) {
            while(end < nums.length && nums[end] == target) {
                end++;
            }
            return --end;
        }
    }

    public static class Merge {
        private final ArrayList<int[]> result = new ArrayList<>();

        private static class Node{
            int val;
            boolean type; // true: start, false: end
            Node(int val, boolean type) {
                this.val = val;
                this.type = type;
            }
        }

        public int[][] merge(int[][] intervals) {
            if(intervals.length <= 1) return intervals;

            ArrayList<Node> nodes = new ArrayList<>();
            for (int[] interval : intervals) {
                nodes.add(new Node(interval[0], true));
                nodes.add(new Node(interval[1], false));
            }
            nodes.sort((o1, o2) -> {
                if(o1.val == o2.val) {
                    if(o1.type && !o2.type) {
                        return -1;
                    }else {
                        return 1;
                    }
                }
                return o1.val - o2.val;
            });

            Stack<Node> stack = new Stack<>();
            while(!nodes.isEmpty()) {
                Node node = nodes.removeFirst();
                if(node.type) {
                    stack.push(node);
                }else {
                    Node top = stack.pop();
                    if(stack.isEmpty()) {
                        this.result.add(new int[]{top.val, node.val});
                    }
                }
            }
            return this.result.toArray(new int[this.result.size()][2]);
        }


    }

    public static class Search {
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int mid = 0;
            while(left <= right) {
                mid = left + (right - left) / 2;
                if(nums[mid] == target) return mid;
                if(nums[left] <= nums[mid]) { // 左侧有序
                    if(target < nums[mid] && target >= nums[left]) { // 元素在左边
                        right = mid - 1;
                    }else {
                        left = mid + 1;
                    }
                }else {// 右侧有序
                    if(target > nums[mid] && target <= nums[right]) { // 元素在右侧
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }

            return -1;
        }
    }

    public static class SearchMatrix {
        public boolean searchMatrix(int[][] matrix, int target) {
            for (int[] ints : matrix) {
                if (binarySearch(ints, target)) {
                    return true;
                }
            }
            return false;
        }

        private boolean binarySearch(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int mid = -1;
            while(left <= right) {
                mid = left + (right - left) / 2;
                if(nums[mid] == target) {
                    return true;
                }

                if(nums[mid] < target) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }

            }
            return false;
        }
    }
}
